package com.comp5900.impl.lcs;

import java.util.*;

public class LongestCommonSubsequenceFinder {

	public static <E> List<E> computeLongestCommonSubsequence(E[] s1, E[] s2) {
		int[][] num = new int[s1.length+1][s2.length+1];
	 
	        for (int i = 1; i <= s1.length; i++)
	                for (int j = 1; j <= s2.length; j++)
	                        if (s1[i-1].equals(s2[j-1]))
	                                num[i][j] = 1 + num[i-1][j-1];
	                        else
	                                num[i][j] = Math.max(num[i-1][j], num[i][j-1]);
	 
	        int s1position = s1.length, s2position = s2.length;
	        List<E> result = new LinkedList<E>();
	 
	        while (s1position != 0 && s2position != 0)
	        {
	                if (s1[s1position - 1].equals(s2[s2position - 1]))
	                {
	                        result.add(s1[s1position - 1]);
	                        s1position--;
	                        s2position--;
	                }
	                else if (num[s1position][s2position - 1] >= num[s1position - 1][s2position])
	                {
	                        s2position--;
	                }
	                else
	                {
	                        s1position--;
	                }
	        }
	        Collections.reverse(result);
	        return result;
	}

	public static void main(String[] args){
		String a = "castle in the sky";
		String b = "cats";

		ArrayList<Character> al, bl;
		al = new ArrayList<Character>();
		bl = new ArrayList<Character>();

		for( char c : a.toCharArray() )
			al.add( Character.valueOf(c) );

		for( char c : b.toCharArray() )
			bl.add( Character.valueOf(c) );

		List<?> l = computeLongestCommonSubsequence(al.toArray(), bl.toArray());

		for(Object c : l)
			System.out.print(c);
	}
}
